LongestIncreasingSubsequence.java

packagesection19_DynamicProgramming;

importjava.util.Arrays;

publicclassLongestIncreasingSubsequence {

publicstaticvoidmain(String[] args) {

// int[] arr = { 3, 4, -1, 0, 6, 2, 3 }; // 4 - LIS {-1,0,2,3}
int[] arr = { 10, 9, 2, 5, 3, 7, 101, 18 }; // 4 - LIS {2,3,7,101}

System.out.println(longestIncSubseq(arr));
 }

// O(n^2) Time | O(n) Space
publicstaticintlongestIncSubseq(int[] arr) {

if (arr.length == 0)
return0;

int[] storage = newint[arr.length];
Arrays.fill(storage, 1);

intans = 1;

for (intidx = 1; idx < arr.length; idx++) {
intcurrMax = 1;

for (intcursor = 0; cursor < idx; cursor++) {
intmax = 1;
if (arr[idx] > arr[cursor]) {
max = 1 + storage[cursor];
 }
if (max > currMax) {
currMax = max;
 }
 }
if (currMax > ans)
ans = currMax;

storage[idx] = currMax;
 }
returnans;
 }
}